package com.动态规划.基础;

public class 整数拆分 {
    public static int integerBreak(int n) {
        //dp[i]表示整数i拆分后的最大乘积
        int[] dp=new int[n+1];
        //初始化dp,dp[0]和dp[1]无意义，舍去
        dp[2]=1;
        //遍历方式:从左到右
        for(int i=3;i<=n;i++){
            for(int j=1;j<i-1;j++){
                dp[i]=Math.max(dp[i],Math.max((i-j)*j,dp[i-j]*j));//递推公式
            }
        }
        //返回结果
        return dp[n];

    }
    public static void main(String[] args) {

    }
}
